package com.leetcode.algorithm.y22.m06;

/**
 * 55. 跳跃游戏
 * 
 * https://leetcode.cn/problems/jump-game/
 * 
 * @author jie.deng
 *
 */
class Question0055Solution02 {

	
	// 贪心算法
	public boolean canJump(int[] nums) {
		// 关键点：不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。
		// 前提条件：
		// 局部最优：每次取最大跳跃步数（取最大覆盖范围）
		// 全局最优：最后得到整体最大覆盖范围，看是否能到终点
		int len = nums.length;

		// 最远可达的下标
		int maxIdx = 0;

		for (int i = 0; i < len && i <= maxIdx; i++) {
			// i <= maxIdx 表示 第i个元素可达
			if (i + nums[i] > maxIdx) {
				maxIdx = i + nums[i];
			}
		}
		return maxIdx >= len - 1;
	}

}